/**
 * \brief Implements a concatenation type HashTable
 * 
 * The data structure is used in the project to create an easy summary
 * inside of the local table.
 * The hashtable contains relative pointers used inside the local table heap pointing
 * various structures.
 * The dataflow used is the following:
 *  -# we retrieve the name of the identifier we need (it might be a function, a class, a local resource);
 *  -# we compute the hash of it;
 *  -# we look inside the hashtable at the position specified by the hash;
 *  -# we picked up the first bytes of the pointer in the memory and we cast it to relative pointer;
 *  -# we retrieve the string pointed by the relative pointer; if the
 *
 * \date Dec 3, 2013
 * \author koldar
 */

#ifndef CONCATHASHTABLE_H_
#define CONCATHASHTABLE_H_

#include "Hash-tools.h"

/**\struct HTRemoteCell
 *
 * The structure represents a single element of a concatenation
 * list inside a concatenation hash table
 *
 */
typedef struct HTRemoteCell {
	/**The next element of the list. NULL if there is none*/
	struct HTRemoteCell* next;
	/**The data stored in the list element*/
	void* data;
} HTRemoteCell;

/**\struct HTLocalCell
 *
 * Represents a cell of a concatenation hashtable.
 * Basically the hashtable is an array of these cells
 *
 */
typedef struct HTLocalCell {
	/**\brief points to the tail of the list
	 *
	 * For each cell of the hashtable, there is a list. To increase the
	 * speed of the append operation of these lists, this value was inserted.
	 * The value points to the last element of the list: in this way append operation are
	 * computed in O(1) (without it, the operation would have taken O(n) instead )
	 */
	Pointer tail;
	/**\brief point to the list itself
	 *
	 * All the elements which share the same hash value are inserted in this list.
	 * TODO add a wikipedia reference to the concatenation hash table
	 */
	HTRemoteCell* list;
} HTLocalCell;

/**\struct Hashtable
 *
 * Represents an hashtable.
 * In the <b>very</b> first field of the HashTable there is the size of the array.
 * This information can be used to quickly get the field "size" from the pointer
 * of the structure
 *
 */
typedef struct HashTable {
	/**the number of cells in the next array behaving as an hashtable
	 *
	 */
	int size;
	/**The actual hashtable
	 *
	 */
	HTLocalCell* hashtable;
} HashTable;

/**\brief Create an hashtable of the given size
 *
 * The function will create an hashtable in which every cell
 * is set to 0. While the function will return basically a pointer,
 * the pointer of the field "hashtable" is
 * the address of the very first cell of the hashtable:
 * so you can handle it just like an array, like this:
 *
 * \code
 * 	//create an hashtable of 25 cells
 * 	HashTable ht=initHashTable(25);
 * 	//set the fourth cell in the hashtable to the value 5
 * 	ht.hashtable[3]=5;
 * 	//some little trick: set the first cell in the hashtable to the value 4
 * 	*ht.hashtable=4;
 * \endcode
 *
 * \pre
 *  \li length must be positive non zero;
 *  \li hashtablePointer: if the parameter is not NULL the memory pointed by
 *  	the parameter must have already been allocated
 * \post
 *  \li a new hashtable is allocated in the memory and should be freed <b>manually</b>
 *   via freeConcatenationHashTable();
 *
 * @param length the number of cells of the hashtable
 * @param hashtablePointer indicates the desired position of this hashtable inside the memory. 2 scenarios:
 *  \li NULL: in this case the hashtable will be allocated in a unkonwn position in the memory;
 *  \li all values but NULL: in this case the table will be allocated precisely at the
 *  	address specified by the parameter. Note that in this case the memory
 *  	must have already been allocated
 * @return a pointer to an hashtable structure
 */
HashTable* initConcatenationHashTable(int length,AbsolutePointer hashtablePointer);

/**\brief adds a relative pointer inside the hashtable.
 *
 * The function stores in the hashtable not the very value to add, but only a
 * value which points to the data; usually it can be:
 *  \li a real pointer (AbsolutePointer);
 *  \li a relative pointer (RelativePointer);
 * The pointer will then be used to get the real value. If the pointer (both
 * relative and absolute) is NULL there will is no further data to retrieve from
 * the concatenation list.
 *
 * \dot
 * 	digraph {
 * 		rankdir="TB";
 * 		subgraph {
 *			rank="same";
 * 			HT [label="hastable cell"];
 * 			c1 [shape="record" label="<f0>next|<f1>pointer to data"];
 * 			c2 [shape="record" label="<f0>next|<f1>pointer to data"];
 * 			c3 [shape="record" label="<f0>next|<f1>pointer to data"];
 * 			c4 [shape="record" label="<f0>NULL|<f1>pointer to data"];
 *
 *	 		HT -> c1;
 *			c1:f0 -> c2;
 *			c2:f0 -> c3;
 *	 		c3:f0 -> c4;
 *		}
 *		data1;
 *		data2;
 *		data3;
 *		data4;
 *
 *		c1:f1 ->data1;
 *		c2:f1 ->data2;
 *		c3:f1 ->data3;
 *		c4:f1 ->data4;
 *	}
 * \enddot
 *
 * \pre
 *  \li ht initialized through initHashTable();
 *  \li id leading to the unique string representing the data to handle. The uniqueness property of this id
 *  	is valid only within the hashtable ht
 *  \li pointerToData must lead to the actual data to store
 *  \li htcellpointer if different from NULL, must be previously allocated.
 *  \li the data was <b>NOT</b> already present in the hashtable. You can check this conditon with lookElementInConcatenationHashTable() function
 * \post
 *  \li value is added to the ht;
 *
 *
 * To use effectively this function you have to:
 * -# select the data to store;
 * -# stores in the memory;
 * -# retrieve the pointer (relative or absolute it doesn't matter) of the data;
 * -# compute the hash of the real data to store (like of the string that identify the data);
 * -# call this function;
 *
 * @param ht the hashtable in which add the value
 * @param id the string representing in a unique way (at least inside the hashtable) the data to store
 * @param pointerToData a pointer to the actual data to store. TRhe data must have as first field a pointer to char
 * 	leading to the identifier of the data itself (for comparison reasons)
 * @param htcellpointer
 * 	\li if equal to NULL indicates that the HTRemoteCell that might be created in the function must be allocated within the whole memory;
 * 	\li otherwise indicates that the HTRemoteCell that might be created in the function MUST write its data at this pointer.
 */
void addElementInConcatenationHashTable(HashTable* ht, char* id,AbsolutePointer pointerToData,AbsolutePointer htcellpointer);

/**\brief Look in the given hash table for a specific value
 *
 * \pre
 *  \li ht initialized correctly with initHashTable();
 *  \li pointerToData must have as first value a char* leading to the id string.
 *  	Used to compare the id with the actual data id
 *
 * @param ht the hash table where to look;
 * @param value the id to search;
 * @return
 * 	\li if the value is found in the hashtable the function returns the pointer
 * 		in the memory where the value is stored;
 * 	\li otherwise it returns NULL;
 *
 */
AbsolutePointer lookElementInConcatenationHashTable(HashTable* ht,char* id);

/**\brief free all the space occupied by the Hashtable
 *
 * The function safely free the data allocated in memory with initHashTable().
 * It also set to NULL the value pointed to ht to ensure the developers can't
 * access to an already free data structures.
 *
 * The function will also free the list pointed by the element inside the hashtable; but
 * not the single data pointed by the elements of the list
 *
 * \dot
 * 	digraph {
 * 		rankdir="LR";
 *		hashtable [shape="record" height="2.5" label="|||||<f0>|||" color="red"];
 *		el1 [shape="record" label="<data>data|<next>next" color="red"];
 *		el2 [shape="record" label="<data>data|<next>next" color="red"];
 *		el3 [shape="record" label="<data>data|<next>next" color="red"];
 *		el4 [shape="record" label="<data>data|<next>next" color="red"];
 *		data1 [label="some data"];
 *		data2 [label="some data"];
 *		data3 [label="some data"];
 *		data4 [label="some data"];
 *
 *		hashtable:f0 -> el1 [color="red"];
 *		el1:next -> el2 [color="red"];
 *		el2:next -> el3 [color="red"];
 *		el3:next -> el4 [color="red"];
 *
 *		el1:data -> data1 [color="red"];
 *		el2:data -> data2 [color="red"];
 *		el3:data -> data3 [color="red"];
 *		el4:data -> data4 [color="red"];
 * 	}
 * \enddot
 *
 * In the figure it is shown exaclty what stuff are freed by this function (red stuff)
 *
 *
 * \pre
 * 	\li *ht initialized through initHashTable();
 * \post
 *  \li *ht is freed;
 *  \li *ht is set to NULL;
 *
 * @param ht a pointer to an already allocated HashTable
 *
 */
void freeConcatenationHashTable(HashTable* ht);


#endif /* CONCATHASHTABLE_H_ */
